package leetcode_141_160;

import java.util.HashMap;

public class maxPoints_149 {
    /**
     * 一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。
     * 求最多有多少个点在同一条直线上。
     */
    public int maxPoints(int[][] points) {
        /**
         * 想法是先尝试暴力遍历每一条直线
         * 使用hashmap存放每一个直线，存放方式是将直线的k和b转化为String类型存为键
         * 发现高解对于斜率的精确度问题的解决方法，我直接采用
         * 36ms
         */
        int ans=0;
        //枚举所有可能的直线
        for(int i=0;i<points.length;i++){
            HashMap<String,Integer>map=new HashMap<>();  //该点所在的所有直线
            int max=0;   //由当前点 i 发出的直线所经过的最多点数量
            for(int t=i+1;t<points.length;t++){
                //不用考虑b的影响，因为此时是基于一个点取遍历其他点
                // 只要斜率一样，这些其他点在一条直线上
                int A=points[i][1]-points[t][1];
                int B=points[i][0]-points[t][0];
                //高解思路，对于斜率，避免出现精度问题，存储为最简分式
                //算出最大公约数
                int k=gcd(A,B);
                String key=A/k+"_"+B/k;
                map.put(key, map.getOrDefault(key, 0) + 1);
                max=Math.max(max,map.get(key));
            }
            ans=Math.max(ans,max+1);  //要加上本身的点
        }
        return ans;
    }

    /**
     * 求最大公因数
     */
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
